package com.lry.basic.algorithm.common;


import java.util.Arrays;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/6/25
 */
public class TopK {
    public static void main(String[] args) {
        int [] arr = {7,1,2,3,5,3,6,1};
        int res = topK2(arr,2);
        System.out.println(res);

    }

    /**
     * 第k大
     * @param arr
     * @param k
     * @return
     */
    private static int topK(int[] arr, int k) {
        int[] temp = new int[k];
        for(int i=0;i<k;i++){
            temp[i] = arr[i];
        }
        Arrays.sort(temp,0,k);
        int t=0;
        for(int i=k;i<arr.length;i++){
            if(arr[i]>temp[0]){
                //小于arr[i]的数前移一位
                for(int j=1;j<k;j++){
                    if(arr[i]>temp[j]){
                        temp[j-1] = temp[j];
                        t=j;
                    }
                }
                temp[t] = arr[i];
            }
        }
        return temp[0];
    }

    private static int topK2(int[] arr,int k){
        int[] temp = new int[k];
        for(int i=0;i<k;i++){
            temp[i] = arr[i];
        }
        //调成最小堆
        for(int i=temp.length/2-1;i>=0;i--){
            sift(temp,i,temp.length-1);
        }
        //遍历后续元素，大于temp[0]就替换并且对堆顶进行一次最小堆调整算法
        for(int i=k;i<arr.length;i++){
            if(arr[i]>temp[0]){
                temp[0] = arr[i];
                sift(temp,0,temp.length-1);
            }
        }
        return temp[0];
    }


    private static void sort(int[]arr){
        for(int i=arr.length/2-1;i>=0;i--){
            sift(arr,i,arr.length-1);
        }
        for(int i=0;i<arr.length;i++){
            swap(arr,0,arr.length-1-i);
            sift(arr,0,arr.length-2-i);
        }
    }

    private static void sift(int[] arr,int k,int m){
        int i = k;
        int j = 2*i+1;
        while(j<=m){
            if(j+1<=m&&arr[j]>arr[j+1]){
                j++;
            }
            if(arr[i]<arr[j])break;
            swap(arr,i,j);
            i = j;
            j = 2*i+1;
        }
    }

    public static  void swap(int[] arr, int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
